package 每日一题;

import 链表.ListNode;

public class No61旋转链表 {

    /**
     * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
     *
     * 示例 1：
     * 输入：head = [1,2,3,4,5], k = 2
     * 输出：[4,5,1,2,3]
     * 示例 2：
     * 输入：head = [0,1,2], k = 4
     * 输出：[2,0,1]
     *  
     * 提示：
     * 链表中节点的数目在范围 [0, 500] 内
     * -100 <= Node.val <= 100
     * 0 <= k <= 2 * 109
     */

    public ListNode rotateRight(ListNode head, int k) {

        if(head==null){
            return null;
        }

        if(k==0){
            return head;
        }

        /**
         * 1.k小于链表长度
         * 2.k大于等于链表长度
         */
        int allLength=0;

        int index=0;
        ListNode fastNode=head;
        while (fastNode!=null&&index<k){
            fastNode=fastNode.next;
            index++;
            allLength++;
        }

        if(fastNode==null){
            //k大于等于链表长度的情况
            fastNode=head;
            k=k%allLength;
            index=0;

            if(k==0){
                return head;
            }

            while (index<k){
                fastNode=fastNode.next;
                index++;
                allLength++;
            }
        }

        ListNode fastLastNode=null;
        ListNode slowLastNode=null;
        ListNode slowNode=head;
        while (fastNode!=null){
            fastLastNode=fastNode;
            fastNode=fastNode.next;
            slowLastNode=slowNode;
            slowNode=slowNode.next;
            allLength++;
        }

        if(k==allLength){
            //k等于链表长度
            return head;
        }else{
            //k小与链表长度,last,slow节点有效
            slowLastNode.next=null;
            fastLastNode.next=head;
            return  slowNode;
        }
    }

    public static void main(String[] args) {
        No61旋转链表 n=new No61旋转链表();
        ListNode listNode = ListNode.createListNode(new int[]{1});
        ListNode result = n.rotateRight(listNode, 1);
        ListNode.printListNode(result);
    }

}
